package org.lintcode_Close.Stage1_Easy_50.O4字符串查找;

/**
 * @Auther: qingle
 * @Date: 2024/8/18-15:37
 * @Description: 对于一个给定的 source 字符串和一个 target 字符串，
 * 你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。
 * 如果不存在，则返回 -1。
 * KMP算法实现
 * @version: 1.0
 */
public class O4字符串查找 {

    /**
     * 在源字符串中查找目标字符串的首次出现位置
     *
     * 这个函数是一个字符串查找函数，用于在源字符串（source）中查找目标字符串（target）的第一次出现的位置。
     * 1)如果找到目标字符串，则返回它在源字符串中的索引位置；
     * 2)如果找不到目标字符串或输入参数为null，则返回-1。
     * 3)该函数首先处理特殊情况：如果目标字符串为空，则返回0；
     * 4)然后计算目标字符串的next数组以优化匹配过程。
     * 5)接下来，使用两个索引i和j遍历源字符串和目标字符串进行匹配。
     * 6)如果源字符串和目标字符串的字符匹配成功，则移动索引到下一个字符；
     * 7)如果匹配失败，则根据next数组更新目标字符串索引j。
     * 8)如果目标字符串完全匹配，则返回目标字符串在源字符串中的起始位置。
     * 9)如果遍历结束仍未找到目标字符串，则返回-1。
     *
     * @param source 源字符串
     * @param target 目标字符串
     * @return 目标字符串在源字符串中首次出现的位置，如果未找到返回-1；如果目标字符串为空字符串，返回0
     */
    public int strStr(String source, String target) {
        // 处理空字符串的情况，直接返回0
        if (target.isEmpty()) {
            return 0;
        }
        // 如果源字符串或目标字符串为null，表示无法进行匹配，返回-1
        if (source == null || target == null) {
            return -1;
        }
        // 计算目标字符串的next数组，用于优化字符串匹配过程
        int[] next = getNext(target);
        // 初始化源字符串和目标字符串的索引
        int i = 0;
        int j = 0;
        // 遍历源字符串和目标字符串，进行匹配
        while (i < source.length() && j < target.length()) {
            // 当匹配失败时，根据next数组决定目标字符串索引j的下一步动作
            if (j == -1 || source.charAt(i) == target.charAt(j)) {
                // 匹配成功，移动索引到下一个字符
                i++;
                j++;
            } else {
                // 匹配失败，根据next数组更新目标字符串索引j
                j = next[j];
            }
            // 如果目标字符串完全匹配，返回目标字符串在源字符串中的起始位置
            if (j == target.length()) {
                return i - j;
            }
        }
        // 如果遍历结束仍未找到目标字符串，返回-1
        return -1;
    }


    /**
     * 计算目标字符串的next数组。
     *
     * 这段代码用于计算一个字符串（称为目标字符串）的next数组。next数组用于字符串匹配时快速确定目标字符串的部分匹配长度，以提高匹配效率。
     * 具体实现如下：
     * 1)初始化next数组，长度与目标字符串相同。
     * 2)next数组的第一个元素设为-1，表示没有匹配的部分。
     * 3)使用两个指针i和j遍历目标字符串，i用于遍历，j表示当前匹配的字符位置。
     * 4)在遍历过程中，如果j为-1或者当前字符匹配，则向后移动i和j，并更新next数组，当前位置i的值为j，表示当前位置之前匹配的字符长度。
     * 5)如果当前字符不匹配，则回退j到之前计算的next值，继续尝试匹配。
     * 6)遍历完成后，返回计算好的next数组。
     * 这个函数常用于KMP（Knuth-Morris-Pratt）算法中，用于优化字符串匹配过程。
     *
     * @param target 目标字符串
     * @return next数组
     */
    private int[] getNext(String target) {
        // 初始化next数组，长度为target字符串的长度
        int[] next = new int[target.length()];
        // next数组的第一个元素初始化为-1，表示没有匹配的部分
        next[0] = -1;
        // i用于遍历目标字符串，j用于表示当前匹配的字符位置
        int i = 0;
        int j = -1;
        // 遍历目标字符串，计算next数组的值
        while (i < target.length() - 1) {
            // 如果j为-1或者当前字符匹配，则继续匹配下一个字符
            if (j == -1 || target.charAt(i) == target.charAt(j)) {
                // 向后移动i和j，准备匹配下一个字符
                i++;
                j++;
                // 更新next数组，当前位置i的值为j，表示当前位置之前匹配的字符长度
                next[i] = j;
            } else {
                // 如果当前字符不匹配，则回退j到之前计算的next值，继续尝试匹配
                j = next[j];
            }
        }
        // 返回计算好的next数组
        return next;
    }


    public static void main(String[] args) {
        O4字符串查找 test = new O4字符串查找();
        System.out.println(test.strStr("abcdefg", "def")); // 输出应为 3
        System.out.println(test.strStr(null, "def")); // 输出应为 3
//        System.out.println(test.strStr("abcdefg", null)); // 输出应为 3
//        System.out.println(test.strStr(null, null)); // 输出应为 3
        System.out.println(test.strStr("abcdefg", "")); // 输出应为 3
        System.out.println(test.strStr("", "")); // 输出应为 3
    }
}
